import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-09-30
 * Time: 21:11
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class Main {
    //方法一:
    //主要分为两节点位于两侧根、同侧
    // public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //     if(root==null){
    //         return null;
    //     }
    //     if(p==root){
    //         return p;
    //     }
    //     if(q==root){
    //         return q;
    //     }
    //     if(q==p){
    //         return p;
    //     }
    //     TreeNode left=lowestCommonAncestor(root.left,p,q);
    //     TreeNode right= lowestCommonAncestor(root.right,p,q);

    //     两节点位于两侧
    //     if(left!=null&&right!=null){
    //         return root;
    //     }

    //     位于同侧
    //     if(left!=null){
    //         return left;
    //     }else{
    //         return right;
    //     }
    // }

    //方法二
    //类似于链表相交求交点
    //难点>>怎样找到路径>>回溯算法>>类似于迷宫问题

    //回溯算法找路径
    public boolean getPath(TreeNode root, TreeNode p,Stack<TreeNode> stack){
        if(root==null){
            return false;
        }
        stack.add(root);
        if(root.val==p.val){
            return true;
        }
        if(getPath(root.left,p,stack)){
            return true;
        }
        if(getPath(root.right,p,stack)){
            return true;
        }
        stack.pop();
        return false;

    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stackP=new Stack<>();
        Stack<TreeNode> stackQ=new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        int sizeP=stackP.size();
        int sizeQ=stackQ.size();
        int step=Math.abs(sizeP-sizeQ);
        //路径长的先走直到两个栈中节点数相同
        if(sizeP>sizeQ){
            for (int i = 0; i < step; i++) {
                stackP.pop();
            }
        }else{
            for (int i = 0; i < step; i++) {
                stackQ.pop();
            }
        }
        //从距离公共祖先相同的位置同时走
        int size=stackP.size();
        for (int i = 0; i < size; i++) {
            TreeNode pNode=stackP.pop();
            TreeNode qNode=stackQ.pop();
            if(pNode.val==qNode.val){
                return pNode;
            }
        }
        return null;
    }

}
